package com.algorithm.order;

import java.util.Arrays;

/**
 * 希尔排序 对插入排序的强化版本
 * 理解不稳定排序，以及步长的概念
 * 相同的元素会产生顺序的改变，不稳定的排序
 *
 * @auth &{zhujiule}
 * @date 2018/7/27
 * @copyright 杭州物恋网科技有限公司
 **/
public class HillOrder {


    public static void main(String args[]){
        shellSort(SERQUENCE);
    }
    private final static int[] SERQUENCE = {21,10,2,3,41,45,11,52,1,23,10,2,3,41,45,11,52,1,23,10,2,3,41,45,11,52,1,23,10,2,3,41,45,11,52,1,23};
    public static void shellSort1() {
        int gap = SERQUENCE.length / 3;

        while (1 <= gap) {
            // 把距离为 gap 的元素编为一个组，扫描所有组
            for (int i = gap; i < SERQUENCE.length; i++) {
                int j = 0;
                int temp = SERQUENCE[i];

                // 对距离为 gap 的元素组进行排序
                for (j = i - gap; j >= 0 && temp < SERQUENCE[j]; j = j - gap) {
                    SERQUENCE[j + gap] = SERQUENCE[j];
                }
                SERQUENCE[j + gap] = temp;
            }

            System.out.format("gap = %d:\t", gap);
            gap = gap / 3; // 减小增量
            printAll();
        }
    }

    private static void printAll(){

        for(int i =0;i<=SERQUENCE.length-1;i++){
            System.out.print(SERQUENCE[i]+"\t");
        }
        System.out.println();
    }
//
//    var len = arr.length,
//
//    temp,
//
//    gap = 1;
//
//    while (gap < len / 3) {         // 动态定义间隔序列
//
//        gap = gap * 3 + 1;
//
//    }
//
//    for (gap; gap > 0; gap = Math.floor(gap / 3)) {
//
//        for (var i = gap; i < len; i++) {
//
//            temp = arr[i];
//
//            for (var j = i-gap; j > 0 && arr[j]> temp; j-=gap) {
//
//                arr[j + gap] = arr[j];
//
//            }
//
//            arr[j + gap] = temp;
//
//        }
//
//    }

//    return arr;

    private static void shellSort(int[] array){
        int len = array.length;
        int gap = len / 3;

        while (1 <= gap) {
            for (int i = gap; i < len; i++) {
                int j = 0;
                int temp = array[i];

                for (j = i - gap; j >= 0 && temp < array[j]; j = j - gap) {
                    array[j + gap] = array[j];
                }
                array[j + gap] = temp;
            }

            System.out.format("gap = %d:\t", gap);
            gap = gap / 3;
            System.out.println(Arrays.toString(array));
        }
    }
}
